ABSTRACT

Graphs are basic requirement of research in many fields like electrical circuits, computer networks, Genome sequencing, traffic flow, compiler design and cryptography to name a few. There are three fundamental issues one has to address in respect of an undirected graph. First, given a number of nodes, how many unique degree sequences can be there to handle? Second, out of these unique degree sequences, how many are graphic? And third, how to generate random graphs for a degree sequence? This paper presents working solutions for all these issues. An efficient algorithm to find all unique degree sequences for a given number of nodes is presented. An algorithm based on Havel-Kasami algorithm is presented which is more efficient than Erdos-Gallai algorithm to test the connectivity. Finally, an algorithm to generate random graphs is also presented.

Keywords: - Adjacency list, connected graph, degree sequence, Erdos-Gallai, Havel-Kasami.